/*
day345 
2020.8.7 
*/
#include<iostream>
#include<cstdlib>
#include<vector>
using namespace std;

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
    	int size=arr.size();
    	int *min_r=new int[size],*max_l=new int[size];
    	
    	max_l[0]=arr[0];
		for(int i=1;i<size;++i)
		{
			max_l[i]=max(max_l[i-1],arr[i]);
		}
		
		min_r[size-1]=arr[size-1];
		for(int i=size-2;i>=0;--i)
		{
			min_r[i]=min(min_r[i+1],arr[i]);
		}
		
		int res=1;
		for(int i=0;i<size-1;++i)
		{
			if(max_l[i]<min_r[i+1])
			{
				res++;
			}
		}
		
		return res;
    }
};


class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        if (arr.empty()) return 0;
        int r = 0;
        int res = 0;
        for (int i = 0; i < arr.size(); ++i) {
            r = max(r, arr[i]);
            if (i == r) {
                ++res;
            }
        }
        return res;
    }
};
int main()
{
	return 0;
}
